﻿#define _CRT_SECURE_NO_WARNINGS 1

#include"PageCache.h" 

PageCache PageCache::_sInst;

// 获取⼀个K⻚的span	//在centralcache加锁
Span* PageCache::NewSpan(size_t k)
{
	assert(k > 0);

	//大于256KB的大块内存申请问题
	//情况二128*8*1024<size	大于128页直接向堆申请
	if (k > NPAGES - 1)
	{
		void* ptr = SystemAlloc(k);
		//此时已经拿到地址了，但为了统一，同时存入map映射方便回收
		//需要设置span
		//Span* span = new Span;
		Span* span = _spanPool.New();
		span->_pageid = (PAGE_ID)ptr >> PAGE_SHIFT;
		span->_n = k;
		//_idSpanMap[span->_pageid] = span;
		_idSpanMap.set(span->_pageid, span);
		return span;
	}

	//先检查第k个桶里面有没有span
	if (!_spanLists[k].Empty())
	{
		//!!!这里也要存_idSpanMap映射
		//! 在centralcache中每一页都要存
		
		Span* kSpan = _spanLists[k].PopFront();
		//建立id和span的映射，方便central cache回收小块内存时，查找对应的span
		for (PAGE_ID i = 0; i < kSpan->_n; i++)
		{
			//_idSpanMap[kSpan->_pageid + i] = kSpan;//只分配一个span,一个span可能包含多个页
			_idSpanMap.set(kSpan->_pageid + i, kSpan);
		}

		return kSpan;
	}
	//第k个桶是空的
	//检查一下后面的桶里面有没有span
	//如果有可以把大的span进行切分
	for (size_t i = k + 1; i < NPAGES; i++)
	{
		if (!_spanLists[i].Empty())
		{
			//切分
			Span* nSpan = _spanLists[i].PopFront();
			//Span* kSpan = new Span;
			Span* kSpan = _spanPool.New();
			//在nSpan的头部切一个k页下来
			//Span按页号标识所有权
			//kSpan返回
			//nSpan链入对应映射位置
			kSpan->_pageid = nSpan->_pageid;
			kSpan->_n = k;		//页的数量

			nSpan->_pageid += k;
			nSpan->_n -= k;

			_spanLists[nSpan->_n].PushFront(nSpan);

			//存储nSpan的首尾页号跟nSpan映射，方便pagecache回收内存时
			//进行合并查找	//只用标识首尾，因为查找时，查前面的尾，查后面的头
			//_idSpanMap[nSpan->_pageid] = nSpan;
			//_idSpanMap[nSpan->_pageid + nSpan->_n - 1] = nSpan;
			_idSpanMap.set(nSpan->_pageid, nSpan);
			_idSpanMap.set(nSpan->_pageid + nSpan->_n - 1, nSpan);

			//建立id和span的映射，方便central cache回收小块内存时，查找对应的span
			for (PAGE_ID i = 0; i < kSpan->_n; i++)
			{
				//_idSpanMap[kSpan->_pageid + i] = kSpan;//只分配一个span,一个span可能包含多个页
				_idSpanMap.set(kSpan->_pageid + i, kSpan);
			}

			//其他Span成员不用处理
			return kSpan;
		}
	}

	//走到这里就说明后面没有大页的span了
	//这时就去找堆要一个128页的span
	//Span* bigSpan = new Span;
	Span* bigSpan = _spanPool.New();
	void* ptr = SystemAlloc(NPAGES - 1);//向堆申请内存
	//不用检查，SystemAlloc函数我们写了抛异常

	//地址向页号转换	//转成整型才能右移
	bigSpan->_pageid = (PAGE_ID)ptr >> PAGE_SHIFT;
	bigSpan->_n = NPAGES - 1;

	_spanLists[bigSpan->_n].PushFront(bigSpan);

	return NewSpan(k);//递归调用 代码复用
}

// 获取从对象到span的映射	自己加锁
Span* PageCache::MapObjectToSpan(void* obj)
{
	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;

	////出了函数作用域自动解锁
	//std::unique_lock<std::mutex> lock(_pageMtx);
	//auto ret = _idSpanMap.find(id);
	//if (ret != _idSpanMap.end())
	//{
	//	return ret->second;
	//	//也可以正常加锁，然后在if else分别解锁
	//}
	//else
	//{
	//	assert(false);//不应该找不到
	//	return nullptr;
	//}

	//!!!!!!!!
	//!!!!!!!!基数树在这里不需要加锁
	//! 1.提前已经把页号对应的空间开好了就不会动结构，不会出现因为插入删除导致找错的情况
	//! 2.只有在ReleaseSpanToPageCache和NewSpan中建立id和span的映射，在central中加锁了
	//!   而且既然不会动结构，只需要防止同时访问同一个span即可，但是不会出现同时访问同一个span情况
	//! 3.读写是分离的，线程1对一个位置读写的时候，线程2不可能对这个位置读写
	auto ret = (Span*)_idSpanMap.get(id);
	assert(ret != nullptr);
	return ret;
}

// 释放空闲span回到Pagecache，并合并相邻的span	centralcache释放到pagecache
void PageCache::ReleaseSpanToPageCache(Span* span)//在centralcache加锁
{
	//大于256KB的大块内存申请问题
	//情况二128*8*1024<size	大于128页直接还给堆
	if (span->_n > NPAGES - 1)
	{
		void* ptr = (void*)(span->_pageid << PAGE_SHIFT);
		SystemFree(ptr);//释放大块内存
		//delete span;//释放new出来的span
		_spanPool.Delete(span);

		return;
	}

	//对span前后的页，尝试进行合并，缓解内存碎片外碎片问题。
						//内碎片其实问题不大，5申请8，还回来，8还能给别人，暂时性问题
	while (1)//向前不断合并
	{
		PAGE_ID previd = span->_pageid - 1;
		//auto ret = _idSpanMap.find(previd);
		////前面的页号没有被申请，不合并了
		//if (ret == _idSpanMap.end())
		//{
		//	break;
		//}
		
		auto ret = (Span*)_idSpanMap.get(previd);
		if (ret == nullptr)
		{
			break;
		}

		//前面相邻页的span在使用，即分配给了central cache
		//Span* prevSpan = ret->second;

		Span* prevSpan = ret;

		if (prevSpan->_isUse == true)
		{
			break;
		}
		//合并出超过NPAGES的span，没法链入哈希桶管理
		if (prevSpan->_n + span->_n > NPAGES - 1)
		{
			break;
		}

		//// prevSpan 是要被合并的 Span
		//_idSpanMap.erase(prevSpan->_pageid);                    // 删除起始页
		//_idSpanMap.erase(prevSpan->_pageid + prevSpan->_n - 1); // 删除结束页
		
		_idSpanMap.set(prevSpan->_pageid, nullptr);                    // 删除起始页
		_idSpanMap.set(prevSpan->_pageid + prevSpan->_n - 1, nullptr); // 删除结束页



		span->_pageid = prevSpan->_pageid;
		span->_n += prevSpan->_n;

		_spanLists[prevSpan->_n].Erase(prevSpan);

		//delete prevSpan;//Span是一个类，通过页号和页数量管理
						//prevSpan所指向的Span已经不存在了，故要delete
		_spanPool.Delete(prevSpan);

		
	}

	//向后合并
	while (1)
	{
		PAGE_ID nextid = span->_pageid + span->_n;
		//auto ret = _idSpanMap.find(nextid);
		////后面的页号没有被申请，不合并了
		//if (ret == _idSpanMap.end())
		//{
		//	break;
		//}
		
		auto ret = (Span*)_idSpanMap.get(nextid);
		if (ret == nullptr)
		{
			break;
		}


		//后面相邻页的span在使用，即分配给了central cache
		//Span* nextSpan = ret->second;
		Span* nextSpan = ret;

		if (nextSpan->_isUse == true)
		{
			break;
		}
		//合并出超过NPAGES的span，没法链入哈希桶管理
		if (nextSpan->_n + span->_n > NPAGES - 1)
		{
			break;
		}

		//// nextSpan 是要被合并的 Span
		//_idSpanMap.erase(nextSpan->_pageid);                    // 删除起始页
		//_idSpanMap.erase(nextSpan->_pageid + nextSpan->_n - 1); // 删除结束页

		_idSpanMap.set(nextSpan->_pageid, nullptr);                    // 删除起始页
		_idSpanMap.set(nextSpan->_pageid + nextSpan->_n - 1, nullptr); // 删除结束页

		span->_n += nextSpan->_n;

		_spanLists[nextSpan->_n].Erase(nextSpan);

		//delete nextSpan;
		_spanPool.Delete(nextSpan);

	}

	//合并后或没合并的span挂入哈希桶
	_spanLists[span->_n].PushFront(span);
	span->_isUse = false;
	//_idSpanMap[span->_pageid] = span;
	//_idSpanMap[span->_pageid + span->_n - 1] = span;
	
	_idSpanMap.set(span->_pageid, span);
	_idSpanMap.set(span->_pageid + span->_n - 1, span);

	//!!!!!!!
	//! 
	//! 这里没有考虑_idSpanMap,可能会导致找到旧的页，非法访问已经释放的span
}